package lanqiaoTraining;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //最大子数组和
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i],nums[i]+dp[i-1]);
            max = Math.max(max,dp[i]);
        }
        return max;
    }

    //环形子数组的最大和
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] fp = new int[n];
        int max = nums[0];
        int min = nums[0];
        int sum = nums[0];
        dp[0] = nums[0];
        fp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i],dp[(i-1)]+nums[i]);
            max = Math.max(max,dp[i]);
            fp[i] = Math.min(nums[i],fp[i-1]+nums[i]);
            min = Math.min(min,fp[i]);
            sum += nums[i];
        }
        if(sum==min){
            return max;
        }
        return Math.max(max,sum-min);
    }

    //乘积最大子数组
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][0];
        dp[0][0] = nums[0]; dp[0][1] = nums[0];
        int max = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(Math.max(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i]),nums[i]);
            dp[i][1] = Math.min(Math.min(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i]),nums[i]);
            max = Math.max(max,Math.max(dp[i][0],dp[i][1]));
        }
        return max;
    }

    //乘积为正数的最长子数组长度
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0]>0?1:0;
        g[0] = nums[0]<0?1:0;
        int max = f[0];
        for (int i = 1; i < n; i++) {
            if(nums[i]==0){
                f[i] = 0;
                g[i] = 0;
            }else if(nums[i]>0){
                f[i] = f[i-1] + 1;
                g[i] = g[i-1]==0?0:g[i-1]+1;
            }else {
                g[i] = f[i-1] + 1;
                f[i] = g[i-1]==0?0:g[i-1]+1;
            }
            max = Math.max(max,f[i]);
        }
        return max;
    }

    //零钱兑换
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int size = coins.length;
        int ret = -1;
        int[] dp = new int[amount+1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            if(i<coins[0]){
                dp[i] = -1;
            }else {
                ret = Integer.MAX_VALUE;
                for (int j = 0; j < size; j++) {
                    if(i>coins[j] && dp[i-coins[j]]!=-1){
                        ret = Math.min(ret,dp[i-coins[j]]+1);
                    }
                }
                dp[i] = ret==Integer.MAX_VALUE?-1:ret;
            }
        }
        return dp[amount];
    }
}
